#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

const int MIN = 0X3f3f3f3f;

int maxProfitIII(int k, const vector<int>& prices) {
    int n = prices.size();

    vector<vector<int>> f(n + 10, vector<int>(k + 10, -MIN));
    vector<vector<int>> g(n + 10, vector<int>(k + 10, -MIN));

    f[1][0] = -prices[0];
    g[1][0] = 0;

    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
            g[i][j] = g[i - 1][j];
            if (j - 1 >= 0)
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i - 1]);
        }
    }

    int ret = 0;
    for (auto e : g[n])
    {
        ret = max(ret, e);
    }

    return ret;
}

int maxProfit(const vector<int>& prices) {
    int n = prices.size();

    vector<vector<int>> f(n + 10, vector<int>(3, -MIN));
    vector<vector<int>> g(n + 10, vector<int>(3, -MIN));

    f[1][0] = -prices[0];
    g[1][0] = 0;

    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);
            g[i][j] = g[i - 1][j];
            if (j - 1 >= 0)
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i - 1]);
        }
    }

    int ret = 0;
    for (auto e : g[n])
    {
        ret = max(ret, e);
    }

    return ret;
}

int main()
{
    maxProfit({ 1,2,3,4,5 });

	return 0;
}